package _021_10_29

func dfs(path []byte, result *[]string, vArr []int, str string) {
	if len(path) == len(vArr) {
		ret := ""
		for i := 0; i < len(path); i++ {
			ret += string(path[i])
		}
		*result = append(*result, ret)
		return
	}

	for i := 0; i < len(vArr); i++ {
		if vArr[i] != 1 {
			path = append(path, str[i])
			vArr[i] = 1
			dfs(path, result, vArr, str)
			path = path[0 : len(path)-1]
			vArr[i] = 0
		}
	}
}

func Permutation(str string) []string {
	var ret []string
	var path []byte
	var vArr []int = make([]int, len(str))
	for i := 0; i < len(vArr); i++ {
		vArr[i] = 0
	}
	dfs(path, &ret, vArr, str)
	checkDoubleResult := map[string]int{}
	chek_arr := make([]int, len(ret))
	for i := 0; i < len(ret); i++ {
		_, ok := checkDoubleResult[ret[i]]
		if ok {
			chek_arr[i] = 1
			continue
		}
		checkDoubleResult[ret[i]] = 1
	}
	newRet := []string{}
	for i := 0; i < len(ret); i++ {
		if chek_arr[i] == 1 {
			continue
		}
		newRet = append(newRet, ret[i])
	}
	return newRet
}
